/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package sumofallprimeunderlimit;

import java.util.Date;

/**
 *Instructions : Compile this Main.java file using java compiler and run it.
 *
 * @author NIRAJ
 *
 * Problem: Determine the sum of all prime numbers less than an "input number" (the input number will be at most 10,000,000).
 *  "Input number" is called as "limit" in the main method.
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        //Set the limit here and execute the code.
        int limit = 1000000;

        //Apprioach one with SpaceComplexity : O(0)
        printSum(limit);

        //Approach two. Faster thn the previous approach.
        printSumSieveWay(limit);
        
    }

     //Approach: Faster
  private static void printSumSieveWay(int limit) {
    long startTime = System.currentTimeMillis();
        boolean[] isPrime = new boolean[limit + 1];

        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i*i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i; i*j <= limit; j++) {
                    isPrime[i*j] = false;
                }
            }
        }

        long sum = 0;
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
               sum = sum + i;
        }

         
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("2. Space complexity might be an issue here, However its much faster");
        System.out.println("Sum: " + sum + ", Time: " + (endTime - startTime) + "ms");

    }

  //This approach Slower but Space complexity is zero.
  private static void printSum(int limit) {
        long sum = 0;

        long startTime = System.currentTimeMillis();

        if(limit >= 2){
            sum = 2;
        }
        for(int i=3; i<=limit; i++){

        boolean flag =false;
                flag = is_Prime(i);

        if(flag){
            sum += i;
       //     System.out.println("Prime: " + i);
         }
        else{
         //   System.out.println("No: " + i);
         }
         i = i+1;
        }
        long endTime = System.currentTimeMillis();
        System.out.println("1. Space complexity: O(0)");
        System.out.println( "Sum " + sum + ", Time: " + (endTime - startTime) + "ms");
    }

  private static boolean is_Prime(int number) {
        if (number <= 1)
            return false;
        int val = (int)Math.sqrt(number);
        for(int i=2; i<=val; i++){
            if(number%i == 0){
                return false;
            }
        }
        return true;
    }


}
